package problems.daily.y2021m7;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author habitplus
 * @since 2021-07-10 10:38
 */
public class T20210710N1 {

}

// 981. 基于时间的键值存储
// 创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：
//      1. set(string key, string value, int timestamp)
//         存储键 key、值 value，以及给定的时间戳 timestamp。
//      2. get(string key, int timestamp)
//         返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp。
//         如果有多个这样的值，则返回对应最大的  timestamp_prev 的那个值。
//         如果没有值，则返回空字符串（""）。
//
// 提示：
//      所有的键/值字符串都是小写的。
//      所有的键/值字符串长度都在 [1, 100] 范围内。
//      所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。
//      1 <= timestamp <= 10^7
//      TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计 120000 次。
//
// 链接：https://leetcode-cn.com/problems/time-based-key-value-store/
class TimeMap {
    private Map<String, List<Node>> data;

    class Node {
        int timestamp;
        String value;
        public Node(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }

    }

    /** Initialize your data structure here. */
    public TimeMap() {
        data = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        List<Node> original = data.getOrDefault(key, new ArrayList<>());
        original.add(new Node(timestamp, value));
        data.put(key, original);
    }

    public String get(String key, int timestamp) {
        String ans = binarySearch(key, timestamp);
        return ans;
    }

    private String binarySearch(String key, int target) {
        List<Node> list = data.getOrDefault(key, new ArrayList<>());
        if (list.size() == 0 || list.get(0).timestamp > target) {
            return "";
        } /* 保证满足条件的目标一定存在 */

        int left = 0, right = list.size() - 1;
        int mid;
        Node node;
        while (left <= right) {
            mid = (right - left) / 2 + left;
            node = list.get(mid);
            if (node.timestamp == target) {
                return node.value;
            } else if (node.timestamp > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return list.get(left - 1).value;
    }
}
